1974E - Money Buys Happiness - CodeForces Solution

ts=int(input())
while ts>0:
    ts-=1
    m,x=map(int,input().split())
    cost=[0]*m
    happy=[0]*m
    for i in range(m):
        cost[i],happy[i]=map(int,input().split())
    total=sum(happy)
    dp=[1000000000000]*(total+5)
    dp[0],ans=0,0
    for i in range(m):
        for j in range(total,happy[i]-1,-1):
            if dp[j-happy[i]]+cost[i]<=i*x:
                dp[j]=min(dp[j],dp[j-happy[i]]+cost[i])
    for i in range(total,0,-1):
        if dp[i]<1000000000000:
            ans=i
            break
    print(ans)